package datastructure.linked;

/**
 * @Description: 单链表定义
 * @author: Yang Qiang
 * @create: 2021-11-02 22:42
 */
public class SingleLinkedList<E> {
    // 虚拟头节点
    private Node dummyHeadNode;
    // 单链表长度
    private int size;

    // 单链表无参构造器
    public SingleLinkedList() {
        dummyHeadNode = new Node();
        size = 0;
    }
    // 获取链表的长度
    public int getSize(){
        return size;
    }
    // 判断链表是否为null
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 单链表进行翻转的方法
     *
     *  解题思路: 需要新创建一个单链表, 用空间换时间, 然后在新链表进行元素翻转拼接, 然后原链表执行新链表即可
     *           移动元素素的话, 我们不采用遍历原链表的方式, 然后从最后一个个的取出来移动到新链表, 这样的时间复杂度不行
     *           我们的做法是把原链表的元素依次拿过来, 然后每次用新链表的虚拟头节点指向
     *
     */
    public void overturn(){
        // 得到原链表的的第一个节点
        Node cur = dummyHeadNode.next;
        // 得到原链表的的第一个节点的下一个节点
        Node next;

        // 创建新链表的虚拟头节点
        Node dummyHeadNode = new Node();

        // 如果当前节点不为空就一直翻转
        while (cur != null){
            // 得到原链表的第一个节点的下一个节点
            next = cur.next;

            // 新链表的虚拟头节点的下一个节点指向原链表的第一个节点的下一个节点
            cur.next = dummyHeadNode.next;

            // 新链表的虚拟头节点的下一个节点指向原链表的第一个节点
            dummyHeadNode.next = cur;

            // 原链表的第一个节点等于原链表的第一个节点的下一个节点
            // 如果下一个节点存在的话, 就会一直循环的翻转节点
            cur = next;
        }

        // 把新链表的虚拟头节点赋值给原链表的虚拟头节点
        // 完成原链表指向新链表
        this.dummyHeadNode = dummyHeadNode;
    }

    /**
     * 往链表中添加元素
     * @param index: 在哪个位置添加元素
     * @param e: 添加的元素
     */
    public void add (int index, E e){
        // 如果添加的位置小于0, 或者大于了链表的长度, 就返回失败
        if (index < 0 || index > size){
            throw new RuntimeException("添加元素失败, 因为添加位置只能大于等于0, 小于等于链表长度");
        }

        // 寻找添加位置的前一个节点, 从虚拟接口开始找
        Node prev = dummyHeadNode;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        // 将指针重新指向
//        Node node = new Node(e);
//        node.next = prev.next;
//        prev.next = node;
        prev.next = new Node(e, prev.next);

        // 链表长度加一
        size++;
    }

    /**
     * 往链条的头添加元素
     * @param e
     */
    public void addFirst(E e){
        add(0 , e);
    }
    /**
     * 往链条的尾添加元素
     * @param e
     */
    public void addLast(E e){
        add(size , e);
    }

    /**
     * 链表查找: 给定索引值, 返回元素
     */
    public E get(int index){
        // 如果查找的位置小于0, 或者大于了链表的长度, 就返回失败
        if (index < 0 || index > size){
            throw new RuntimeException("查找元素失败, 因为查找位置只能大于等于0, 小于等于链表长度");
        }

        // 从虚拟头节点的下一个节点开始找
        Node node = dummyHeadNode.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }

        return node.e;
    }
    // 查找第一个元素
    public E getFirst(){
        return get(0);
    }
    // 查找最后一个元素
    public E getLast(){
        return get(size-1);
    }

    /**
     * 判断链表是否包含指定元素
     */
    public boolean contains(E e ){
        // 得到第一个节点
        Node node = dummyHeadNode.next;
        // 节点不为null, 就一直找
        while (node != null){
            if (e.equals(node.e)) return true;
            node = node.next;
        }
        return false;
    }

    /**
     * 修改指定位置节点的元素
     */
    public void update(int index, E e){
        // 如果修改的位置小于0, 或者大于了链表的长度, 就返回失败
        if (index < 0 || index > size){
            throw new RuntimeException("修改元素失败, 因为修改位置只能大于等于0, 小于等于链表长度");
        }

        // 先找到指定位置的节点 -> 从虚拟头节点的下一个节点开始找
        Node node = dummyHeadNode.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        node.e = e;
    }
    /**
     * 链表的删除, 并返回值
     */
    public E delete(int index){
        // 如果删除的位置小于0, 或者大于了链表的长度, 就返回失败
        if (index < 0 || index > size){
            throw new RuntimeException("删除元素失败, 因为删除位置只能大于等于0, 小于等于链表长度");
        }

        // 先找到删除节点的前一个节点
        Node node = dummyHeadNode;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        Node delNode = node.next;

        // 改变指针
        node.next = delNode.next;
        delNode.next = null;// 让这个节点没有被引用, 就会被删除了

        size--;

        // 返回删除的节点
        return delNode.e;

    }

    /**
     * 删除第一个元素
     */
    public E deleteFirst(){
        return delete(0);
    }

    /**
     * 删除最后一个元素
     */
    public E deleteLast(){
        return delete(size);
    }

    /**
     * 给定这个元素, 然后删除这个元素
     */
    public void removeNode(E e){
        // 找到这个元素的前一个元素
        Node node = dummyHeadNode;
        while (node.next != null){
            if (e.equals(node.next.e)) break;
            node = node.next;
        }

        // 找到的元素不为null, 就删除
        if (node.next != null){
            Node delNode = node.next;
            node.next = delNode.next;
            delNode.next = null;
            size--;
        }
    }

    /**
     * 定义节点Node对象
     */
    public class Node {
        // 数据域
        public E e;
        // 指针域
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node() {
            this.e = null;
            this.next = null;
        }

        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
        Node cur = dummyHeadNode.next;
        while (cur!=null){
            builder.append(cur+"->");
            cur = cur.next;
        }
        builder.append("NULL");
        return builder.toString();
    }

}
